package model;

import java.util.ArrayList;
import java.util.List;

/**
 * create by yongli on 2020-07-21 22:23
 * 自己定义数据结构，实现一个图的存取遍历
 */

public class Graph<T> {
    private List<Node<T>> nodes;

    // 广度优先搜索
    public void BSvisit() {
        boolean[] flags = new boolean[nodes.size()];
        while (true) {
            for (int i = 0; i < nodes.size(); i++) {
                Node<T> node = nodes.get(i);
                T data = node.getData();
                System.out.println(data);
                flags[i] = true;

                // 访问邻节点
                List<Node<T>> nearList = node.getNearList();
                for (Node<T> tNode : nearList) {
                    T data1 = tNode.getData();
                    System.out.println(data1);
                    int idx = nodes.indexOf(tNode);
                    flags[idx] = true;
                }
            }
            // 是否访问完所有节点,亦即所有的节点都为true,已经访问的节点计数
            int n = 0;
            for (boolean flag : flags) {
                if (flag) {
                    n++;
                }
            }
            if (n == nodes.size()) {
                break;
            }
        }
    }

    // 增加节点并创建关联关系，使用已有节点的的索引
    public void addNodeAndRel(Node<T> node, List<Integer> nodeIdx) {
        nodes.add(node);
        for (int idx : nodeIdx) {
            node.addNearNode(nodes.get(idx));
        }
    }


}

// 图中节点的数据结构,采用简单的无向图
class Node<T> {
    private T data;
    private List<Node<T>> nearList;

    public Node(T data) {
        this.data = data;
        nearList = new ArrayList<>();
    }

    public boolean addNearNode(Node node) {
        return nearList.add(node);
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public List<Node<T>> getNearList() {
        return nearList;
    }
}

